package com.yu1996.linkedlist;

import java.util.Stack;

public class SingleLinkedListDemo {

    public static void main(String[] args) {
        HeroNode heroNode1 = new HeroNode(1, "张三", "老张");
        HeroNode heroNode2 = new HeroNode(2, "李四", "老李");
        HeroNode heroNode3 = new HeroNode(3, "王五", "老王");
        HeroNode heroNode4 = new HeroNode(4, "王五", "老王");
        HeroNode heroNode5 = new HeroNode(5, "王五", "老王");
        HeroNode heroNode6 = new HeroNode(6, "王五", "老王");

        SingleLinkedList list = new SingleLinkedList();
        SingleLinkedList list1 = new SingleLinkedList();
//        测试增加节点
        list.add(heroNode1);
        list.add(heroNode3);
        list.add(heroNode5);

        list1.add(heroNode2);
        list1.add(heroNode4);
        list1.add(heroNode6);
//        测试有序增加节点
//        list.addByOrder(heroNode3);
//        list.addByOrder(heroNode1);
//        list.addByOrder(heroNode2);
//        测试输出链表
//        list.list();

//        测试修改节点
//        System.out.println("修改后的-----");
//        heroNode1.name = "张小三";
//        heroNode1.nickName = "小张";
//        list.update(heroNode1);
        list.list();
        System.out.println("这是第二个链表------");
        list1.list();
//        测试删除节点
//        list.delete(1);
//        list.delete(2);
//        list.delete(3);
//        System.out.println("删除后的-------");
//        list.list();


//        测试获得链表总长度
//        System.out.println(SingleLinkedList.getLength(list.getHead()));


//        测试输出链表倒数第几个节点
//        HeroNode lastIndexNode = SingleLinkedList.findLastIndexNode(list.getHead(), 3);
//        System.out.println("节点是:" + lastIndexNode);


        //测试输出逆序链表
//        SingleLinkedList.changeList(list.getHead());
//        System.out.println("==========================================");
//        list.list();

//        测试链表逆序打印
//        System.out.println("这是逆序之后--------------");
//        SingleLinkedList.printByChange(list.getHead());
//        System.out.println("这是原来的链表 --------------");
//        list.list();

//        测试合并有序的两个链表
        HeroNode heroNode = SingleLinkedList.connectionTwoListOrderly(list.getHead(), list1.getHead());
        SingleLinkedList list2 = new SingleLinkedList(heroNode);
        System.out.println("这是合并后的--------");
        list2.list();
    }
}


class SingleLinkedList {

    //定义头结点 （头结点不要动，不存放具体数据）
    private HeroNode head = new HeroNode(0, "", "");

    public SingleLinkedList(HeroNode head) {
        this.head = head;
    }

    public SingleLinkedList() {
    }

    /**
     * @Description 添加新的节点
     * @Author xing
     * @Date 2019/7/27 22:43
     * @Param
     * @Return
     * @Exception
     */
    public void add(HeroNode node) {

        //添加一个新的节点用于辅助遍历
        HeroNode temp = head;

        //循环遍历到最后一个节点位置
        while (true) {

            if (temp.next == null) {
                break;
            }
            temp = temp.next;
        }
        //将需要插入的节点插入
        temp.next = node;
    }


    /**
     * @Description 根据编号排序添加新节点
     * @Author xing
     * @Date 2019/7/27 22:44
     * @Param
     * @Return
     * @Exception
     */
    public void addByOrder(HeroNode node) {

        //添加一个新的节点用于辅助遍历
        HeroNode temp = head;
        //定义标准是否重复插入  默认为false
        boolean flage = false;
        //找打编号对应的位置
        while (true) {

            //说明插入节点的编号为当前编号的最大值
            if (temp.next == null) {
                break;
            }
            //说明temp找到当前插入的位置
            if (temp.next.no > node.no) {
                break;
            } else //说明插入编号已经存在
                if (temp.next.no == node.no) {
                    flage = true;
                    break;
                }
            temp = temp.next;
        }
        //判断是否重复插入
        if (flage) {
            System.out.printf("插入编号%d已经存在，不能重复插入\n", node.no);
            return;
        }
        node.next = temp.next;
        temp.next = node;
    }


    /**
     * @Description 更新某个节点
     * @Author xing
     * @Date 2019/7/27 22:44
     * @Param
     * @Return
     * @Exception
     */
    public void update(HeroNode newNode) {
        //判断链表是否为空
        if (head.next == null) {
            System.out.println("当前链表为空，请先添加数据");
            return;
        }
        //添加一个新的节点用于辅助遍历
        HeroNode temp = head.next;
        //用于判断是否找到标号相同的节点
        boolean flag = false;
        while (true) {
            if (temp == null) {
                break;
            }
            if (temp.no == newNode.no) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            temp.name = newNode.name;
            temp.nickName = newNode.nickName;
        } else {
            System.out.printf("没有找到编号为%d的节点,无法修改\n", newNode.no);
        }
    }


    /**
     * @Description 删除某个节点（根据no编号删除）
     * @Author xing
     * @Date 2019/7/27 22:44
     * @Param
     * @Return
     * @Exception
     */
    public void delete(int no) {
        //判断链表是否为空
        if (head.next == null) {
            System.out.println("当前链表为空，请先添加数据");
            return;
        }
        //添加一个新的节点用于辅助遍历
        HeroNode temp = head;
        //用于判断是否找到编号相同的节点
        boolean flag = false;
        while (true) {
            //temp当前为最后一个节点，跳出循环，未找到需要删除的节点
            if (temp.next == null) {
                break;
            }
            if (temp.next.no == no) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            temp.next = temp.next.next;
        } else {
            System.out.printf("没有找到编号为%d的节点,无法删除\n", no);
        }
    }


    /**
     * @Description 输出当前链表
     * @Author xing
     * @Date 2019/7/27 22:45
     * @Param
     * @Return
     * @Exception
     */
    public void list() {
        //判断链表是否为空
        if (head.next == null) {
            System.out.println("当前链表为空，请先添加数据");
            return;
        }

        //添加一个新的节点用于辅助遍历
        HeroNode temp = head.next;
        while (true) {
            if (temp == null) {
                break;
            }
            System.out.println(temp);
            temp = temp.next;
        }
    }


    //获得头结点
    public HeroNode getHead() {
        return head;
    }

    /**
     * @Description 获得当前链表的有效长度
     * @Author xing
     * @Date 2019/7/27 22:47
     * @Param
     * @Return
     * @Exception
     */
    public static int getLength(HeroNode head) {
        //判断链表是否为空
        if (head.next == null) {
            return 0;
        }
        //定义总长度
        int length = 0;
        //定义新节点 辅助遍历
        HeroNode temp = head.next;
        while (true) {
            if (temp == null) {
                break;
            }
            length++;
            temp = temp.next;
        }
        return length;
    }


    /**
     * @Description 输出当前链表倒数第几个节点
     * @Author xing
     * @Date 2019/7/29 10:50
     * @Param
     * @Return
     * @Exception
     */
    public static HeroNode findLastIndexNode(HeroNode head, int index) {
        //判断链表是否为空
        if (head.next == null) {
            return null;
        }

        //判断一下输入的数据是否合法
        if (index > getLength(head)) {
            System.out.println("输入不合法");
            return null;
        }
        //定义新节点 辅助遍历
        HeroNode temp = head.next;
        for (int i = 0; i < getLength(head) - index; i++) {
            temp = temp.next;
        }
        return temp;
    }


    /**
     * @Description: 链表的翻转（遍历接链表，依次插入新链表的第一个位置）
     * @author: xing
     * @Date: 2019/8/2 9:27
     */
    public static void changeList(HeroNode head) {
        //判断当前链表是否为空或者就一个元素   直接返回
        if (head.next == null || head.next.next == null) {
            return;
        }
        //定义辅助节点遍历原链表
        HeroNode front = head.next;
        //定义辅助节点遍历新链表
        HeroNode next = null;
        //定义新链表的头结点
        HeroNode resHead = new HeroNode(0, "", "");
        //先遍历原来的链表  将每一个节点加入新链表的第一个位置
        while (true) {
            //当当前节点为最后一个时跳出
            if (front == null) {
                break;
            }
            //将next节点赋值到front节点之后    每次循环都需要
            next = front.next;
            //先将旧的节点连接新链表后面的节点
            front.next = resHead.next;
            //将front节点连接到新链表的后面
            resHead.next = front;
            //连接完成后将front节点再次指向原链表
            front = next;

        }
        head.next = resHead.next;
    }

    public static void printByChange(HeroNode head) {
        //判断当前链表是否为空或者就一个元素   直接返回
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        //定义辅助节点遍历原链表
        HeroNode temp = head.next;
        //定义一个栈
        Stack stack = new Stack();
        //先遍历原来的链表  将每一个节点压入栈中
        while (temp != null) {
            stack.add(temp);
            temp = temp.next;
        }
        while (stack.size() > 0) {
            System.out.println(stack.pop());
        }
    }


    /**
     * @Description: 合并两个有序的链表（按照no排序）
     * @author: xing
     * @Date: 2019/8/2 10:00
     */
    public static HeroNode connectionTwoListOrderly(HeroNode head1, HeroNode head2) {
        //判断是否为空
        if (head1.next == null || head2.next == null) {
            return head1 == null ? head2 : head1;
        }

        //定义辅助节点遍历链表1
        HeroNode temp1 = head1.next;
        //定义辅助节点遍历链表2
        HeroNode temp2 = head2.next;
        //新建链表用于合并两个链表
        HeroNode head = new HeroNode(0, "", "");
        //定义辅助节点遍历新链表
        HeroNode temp = head;
        while (true) {
            if (temp1 == null || temp2 == null) {
                break;
            }
            if (temp1.no <= temp2.no) {
                temp.next = temp1;
                temp1 = temp1.next;
            } else {
                temp.next = temp2;
                temp2 = temp2.next;
            }
            temp = temp.next;
        }
        if (temp1 != null) {
            temp.next = temp1;
        }
        if (temp2 != null) {
            temp.next = temp2;
        }

        return head;


//        //递归结束条件
//        if (head1 == null && head2 == null) {
//            return null;
//        }
//        if (head1 == null) {
//            return head2;
//        }
//        if (head2 == null) {
//            return head1;
//        }
//        //合并后的链表
//        HeroNode head = null;
//        if (head1.no > head2.no) {
//            //把head较小的结点给头结点
//            head = head2;
//            //继续递归head2
//            head.next = connectionTwoListOrderly(head1, head2.next);
//        } else {
//            head = head1;
//            head.next = connectionTwoListOrderly(head1.next, head2);
//        }
//        return head;

    }

}


/**
 * @Description: 定义节点
 * @author: xing
 * @Date: 2019/7/27 22:45
 */
class HeroNode {
    public int no; //编号
    public String name; //姓名
    public String nickName; //别名
    public HeroNode next;  //下一个节点

    public HeroNode(int no, String name, String nickName) {
        this.no = no;
        this.name = name;
        this.nickName = nickName;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickName='" + nickName + '\'' +
                '}';
    }
}
